package sort;

/**
 * 归并排序
 */
public class mergeSort {
    public static void main(String[] args) {
        int[] arr = {3,32,43,5,6,4,3};
        process(arr,0,6);
    }
    public static void process(int[] arr,int L,int R){
        if (L == R){
            return;
        }
        int Middle = L + ((R - L)>>1);
        process(arr,L,Middle);
        process(arr,Middle+1,R);
        mergin(arr,L,Middle,R);
    }
    public static void mergin(int[] arr,int L,int Middle,int R){
        int[] temp = new int[R - L + 1];
        int index = 0;
        int left = L;
        int right = Middle+1;
        while (left <= Middle && right <= R){
            if (arr[left] <= arr[right]){
                temp[index++] = arr[left++];
            }else{
                temp[index++] = arr[right++];
            }
        }
        while (right <= R){
            temp[index++] = arr[right++];
        }
        while (left <= Middle){
            temp[index++] = arr[left++];
        }
        for (int i = L;i <= R; i++) {
            arr[i] = temp[i-L];
        }
    }
}
